
<!DOCTYPE html>
<html>
  <head>
    <title>Big-O Algorithm Complexity Cheat Sheet</title>
    
    <link href="https://cdnjs.cloudflare.com/ajax/libs/normalize/4.2.0/normalize.min.css" rel="stylesheet">
    <link href="css/main.css" rel="stylesheet">
  </head>
  <body>
    <div id="header"> 
      <a id="logo" href="#">Big-O Cheat Sheet</a>
      <!-- <a id="download" href="pdf/big-o-cheatsheet.pdf" download="big-o-cheatsheet.pdf">Download PDF</a> -->
    </div>

    <div id="page">
        <h2 id="chartTitle">Big-O Complexity Chart</h2>

        <div>
          <table id="legend" class="table">
            <tbody>
              <tr>
                <td><code class="red">Horrible</code></td>
                <td><code class="orange">Bad</code></td>
                <td><code class="yellow">Fair</code></td>
                <td><code class="yellow-green">Good</code></td>
                <td><code class="green">Excellent</code></td>
              </tr>
            </tbody>
          </table> 
        </div>

        <div>
          <svg id="chart" width="800" height="500" xmlns="http://www.w3.org/2000/svg">
            <!-- horrible region -->
            <path d="M50 450 L 50 0 L 800 0 L 800 450 Z" fill="#ff8989"/>
            <!-- bad region -->
            <path d="M50 450 L 800 0 L 800 450 Z" fill="#FFC543"/>
            <!-- fair region -->
            <path d="M50 450 L 800 450 L 800 330 Z" fill="yellow"/>
            <!-- good region -->
            <path d="M50 450 L 800 450 L 800 410 Z" fill="#C8EA00"/>
            <!-- excellent region -->
            <path d="M50 450 L 800 450 L 800 440 Z" fill="#53d000"/>

            <!-- axes -->
            <path d="M50 0 L 50 450 L 800 450" fill="transparent" stroke="black" stroke-width="2"/>

            <path d="M50 448 L 800 448" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="700" y="438" fill="black">O(log n), O(1)</text>

            <path d="M50 450 L 800 400" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="760" y="390" fill="black">O(n)</text>

            <path d="M50 450 Q 400 350, 800 150" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="630" y="190" fill="black">O(n log n)</text>

            <path d="M50 450 Q 180 380, 250 0" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="260" y="30" fill="black">O(n^2)</text>

            <path d="M50 450 C 100 430, 120 350, 120 0" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="125" y="20" fill="black">O(2^n)</text>

            <path d="M50 450 C 80 450, 80 350, 80 0" fill="transparent" stroke="black" stroke-width="2"/>
            <text x="80" y="20" fill="black">O(n!)</text>

            <text x="0" y="0" transform="translate(30 230) rotate(-90)" style="dominant-baseline: middle; text-anchor: middle; font-size:20px; color: #555; font-size:20px; color: #555; font-style: italic;" fill="black">Operations</text>
            <text x="0" y="0" transform="translate(420 470)" style="dominant-baseline: middle; text-anchor: middle; font-size:20px; color: #555; font-style: italic;" fill="black">Elements</text>
          </svg>
        </div>

      <div id="tablesWrapper">
        <h2 id="data-structures">Common Data Structure Operations</h2>
<table class="table table-bordered table-striped">

    <tr>
      <th>数据结构</th>
      <th colspan="8">时间复杂度</th>
      <th>空间复杂度</th>
    </tr>
    <tr>
      <th></th>
      <th colspan="4">平均</th>
      <th colspan="4">最差</th>
      <th>最差</th>
    </tr>
    <tr>
      <th></th>
      <th>访问</th>
      <th>搜索</th>
      <th>插入</th>
      <th>删除</th>
      <th>访问</th>
      <th>搜索</th>
      <th>插入</th>
      <th>删除</th>
      <th></th>
    </tr>

    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Array_data_structure">数组</a></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Stack_(abstract_data_type)">栈</a></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Queue_(abstract_data_type)">队列</a></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Singly_linked_list#Singly_linked_lists">单向链表</a></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Doubly_linked_list">双向链表</a></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="yellow">&Theta;(n)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="green">O(1)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Skip_list">跳表</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="orange">O(n log(n))</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Hash_table">哈希表</a></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="green">&Theta;(1)</code></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Binary_search_tree">二叉搜索树</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="https://en.wikipedia.org/wiki/Cartesian_tree">笛卡尔树</a></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/B_tree">B树</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Red-black_tree">红黑树</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="https://en.wikipedia.org/wiki/Splay_tree">伸展树</a></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="gray">N/A</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/AVL_tree">AVL树</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/K-d_tree">KD树</a></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow-green">&Theta;(log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>

</table>

<h2 id="sorting">数组排序算法</h2>
<table class="table table-bordered table-striped">
    <tr>
      <th>算法</th>
      <th colspan="3">时间复杂度</th>
      <th>空间复杂度</th>
    </tr>
    <tr>
      <th></th>
      <th>最好</th>
      <th>平均</th>
      <th>最差</th>
      <th>最差</th>
    </tr>

    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a></td>
      <td><code class="orange">&Omega;(n log(n))</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="yellow-green">O(log(n))</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Merge_sort">Mergesort</a></td>
      <td><code class="orange">&Omega;(n log(n))</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="orange">O(n log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Timsort">Timsort</a></td>
      <td><code class="yellow">&Omega;(n)</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="orange">O(n log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Heapsort">Heapsort</a></td>
      <td><code class="orange">&Omega;(n log(n))</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="orange">O(n log(n))</code></td>
      <td><code class="green">O(1)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Bubble_sort">Bubble Sort</a></td>
      <td><code class="yellow">&Omega;(n)</code></td>
      <td><code class="red">&Theta;(n^2)</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="green">O(1)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Insertion_sort">Insertion Sort</a></td>
      <td><code class="yellow">&Omega;(n)</code></td>
      <td><code class="red">&Theta;(n^2)</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="green">O(1)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Selection_sort">Selection Sort</a></td>
      <td><code class="red">&Omega;(n^2)</code></td>
      <td><code class="red">&Theta;(n^2)</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="green">O(1)</code></td>
    </tr>
    <tr>
      <td><a href="https://en.wikipedia.org/wiki/Tree_sort">Tree Sort</a></td>
      <td><code class="orange">&Omega;(n log(n))</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a href="http://en.wikipedia.org/wiki/Shellsort">Shell Sort</a></td>
      <td><code class="orange">&Omega;(n log(n))</code></td>
      <td><code class="red">&Theta;(n(log(n))^2)</code></td>
      <td><code class="red">O(n(log(n))^2)</code></td>
      <td><code class="green">O(1)</code></td>
    </tr>
    <tr>
      <td><a rel="tooltip" title="Only for integers. k is a number of buckets" href="http://en.wikipedia.org/wiki/Bucket_sort">Bucket Sort</a></td>
      <td><code class="green">&Omega;(n+k)</code></td>
      <td><code class="green">&Theta;(n+k)</code></td>
      <td><code class="red">O(n^2)</code></td>
      <td><code class="yellow">O(n)</code></td>
    </tr>
    <tr>
      <td><a rel="tooltip" title="Constant number of digits 'k'" href="http://en.wikipedia.org/wiki/Radix_sort">Radix Sort</a></td>
      <td><code class="green">&Omega;(nk)</code></td>
      <td><code class="green">&Theta;(nk)</code></td>
      <td><code class="green">O(nk)</code></td>
      <td><code class="yellow">O(n+k)</code></td>
    </tr>
    <tr>
      <td><a rel="tooltip" title="Difference between maximum and minimum number 'k'" href="https://en.wikipedia.org/wiki/Counting_sort">Counting Sort</a></td>
      <td><code class="green">&Omega;(n+k)</code></td>
      <td><code class="green">&Theta;(n+k)</code></td>
      <td><code class="green">O(n+k)</code></td>
      <td><code class="yellow">O(k)</code></td>
    </tr>
    <tr>
      <td><a href="https://en.wikipedia.org/wiki/Cubesort">Cubesort</a></td>
      <td><code class="yellow">&Omega;(n)</code></td>
      <td><code class="orange">&Theta;(n log(n))</code></td>
      <td><code class="orange">O(n log(n))</code></td>
      <td><code class="yellow">O(n)</code></td>
   </tr>

</table>
      </div>

    </div>

  </body>
</html>
